class Solution {//leetcode329——矩阵中的最长递增路径
private:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int dfs(vector<vector<int>>&matrix,int i,int j){
        if(memory[i][j]!=0) return memory[i][j];
        int ret=1;
        for(int k=0;k<4;k++){
            int x=j+dx[k];
            int y=i+dy[k];
            if(x>=0&&x<n&&y>=0&&y<m&&matrix[i][j]<matrix[y][x]){
                ret=max(ret,dfs(matrix,y,x)+1);
            }
        }
        memory[i][j]= ret;
        return memory[i][j];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m=matrix.size();
        n=matrix[0].size();
        memory.resize(m,vector<int>(n,0));
        int ret=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                ret=max(ret,dfs(matrix,i,j));    
            }

        return ret;
    }
private:
    int m;
    int n;
    vector<vector<int>> memory;
};